package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:字母异位词分组
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 * User:Mr.Du
 * Date:2023/9/18
 * Time:21:21
 */
public class GroupAnagrams {

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        List<String> list = new ArrayList<>();
        list.add(strs[0]);
        res.add(list);
        for(int i = 1;i < strs.length;i++){
            boolean flag = true;
            for(int j = 0;j < res.size();j++){
                if(isEqual(res.get(j).get(0), strs[i])){
                    res.get(j).add(strs[i]);
                    flag = false;
                    break;
                }
            }
            if(flag){
                list = new ArrayList<>();
                list.add(strs[i]);
                res.add(list);
            }
        }
        return res;
    }

    public boolean isEqual(String s1, String s2){
        int l1 = s1.length(), l2 = s2.length();
        if(l1 != l2) return false;
        int[] arr = new int[26];
        for(int i = 0;i < l1;i++){
            arr[s1.charAt(i) - 'a']++ ;
        }
        for(int i = 0;i < l1;i++){
            arr[s2.charAt(i) - 'a']--;
        }
        for(int i = 0;i < 26;i++){
            if(arr[i] != 0) return false;
        }
        return true;
    }

    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List<String>> codeToGroup = new HashMap<>();
        // 编码相同的放入map中
        for (String s : strs) {
            // 对字符串进行编码
            String code = encode(s);
            // 把编码相同的字符串放在一起
            codeToGroup.putIfAbsent(code, new LinkedList<>());
            codeToGroup.get(code).add(s);
        }

        // 获取结果
        List<List<String>> res = new LinkedList<>();
        for (List<String> group : codeToGroup.values()) {
            res.add(group);
        }

        return res;
    }

    // 利用每个字符的出现次数进行编码
    String encode(String s) {
        char[] count = new char[26];
        for (char c : s.toCharArray()) {
            int delta = c - 'a';
            count[delta]++;
        }
        return new String(count);
    }
}
